package com.ma.array;

import java.util.Stack;

/**
 * @ClassName Solution316
 * @Author: mayongqiang
 * @DATE 2022/3/29 9:46
 * @Description: 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 */
public class Solution316 {
    public static void main(String[] args) {
        /*
        输入：s = "bcabc"
        输出："abc

        输入：s = "cbacdcbc"
        输出："acdb"
         */
        String s = "bcabc";
        System.out.println(removeDuplicateLetters(s));
        System.out.println(removeDuplicateLetters("cbacdcbc"));

    }

    /**
     * 1、需要去重，去重后不能改变字符在字符串的原始位置
     * 2、需要返回的字典序最小
     */
    public static String removeDuplicateLetters(String s) {
        // 用栈来实现
        Stack<Character> stack = new Stack<>();
        boolean[] inStack = new boolean[256];

        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }

        for (Character c : s.toCharArray()) {
            count[c]--;
            if (inStack[c]) {
                continue;
            }
            // 在往栈中插入某个元素的时候，判断它的字典序和之前进去的大小  如果要插入的比之前的小，要把这个放前面

            while (!stack.isEmpty() && stack.peek() > c) {
                // 删除时还要考虑这个元素后面会不会出现
                /*
                 * 情况一、如果stk.peek()这个字符之后还会出现，那么可以把它 pop 出去，反正后面还有嘛，后面再 push 到栈里，刚好符合字典序的要求。
                    情况二、如果stk.peek()这个字符之后不会出现了，前面也说了栈中不会存在重复的元素，那么就不能把它 pop 出去，否则你就永远失去了这个字符。
                 */
                if (count[stack.peek()] == 0) {
                    break;
                }
                inStack[stack.pop()] = false;
            }

            stack.push(c);
            inStack[c] = true;
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();


    }
}
